// //js二叉树手写题
// ## JavaScript二叉树遍历题目
//
// **题目：二叉树的层序遍历**
//
// ### 题目描述
// 给定一个二叉树的根节点 `root`，返回其节点值的层序遍历结果。层序遍历是指按照层级顺序，从左到右访问所有节点。
//
// ### 示例
//     ```
// 输入: root = [3,9,20,null,null,15,7]
// 输出: [[3],[9,20],[15,7]]
//
// 输入: root = [1]
// 输出: [[1]]
//
// 输入: root = []
// 输出: []
// ```
//
//
// ### 要求
// - 实现函数 `levelOrder(root)`
// - 返回二维数组，每个子数组代表一层的节点值
// - 时间复杂度要求：O(n)
// - 空间复杂度要求：O(n)
//
// ### 提示
// - 树中节点数目在范围 [0, 2000] 内
// - -1000 <= Node.val <= 1000
//
// 你可以使用广度优先搜索(BFS)或者深度优先搜索(DFS)来解决这个问题。

function levelOrder(root) {
    if(!root) return [];
    const queue = [root];
    const result = [];
    while(queue.length > 0){
        const level = [];
        for(let i = queue.length; i > 0; i--){
            const node = queue.shift();
            level.push(node.val);
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        }
        result.push(level);
    }
    return result;
}

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
console.log(levelOrder(root));

